class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:
        pl = []
        isPrime = [True] * 100000
        tot = 0
        for i in range(2, r + 1):
            if isPrime[i]:
                pl.append(i)
                if i * i >= l and i * i <= r:
                    tot += 1
            for p in pl:
                if p * i >= r + 1:
                    break
                isPrime[p * i] = False
                if i % p == 0:
                    break
            if i * i > r:
                break
        return r - l + 1 - tot


s = Solution()
print(s.nonSpecialCount(2879, 52145))


# class PrimeFactor:

#     def __init__(self, ceil):
#         self.ceil = ceil  # 上限
#         self.prime_factor = [[] for _ in range(self.ceil + 1)]  # 因数列表
#         self.min_prime = [0] * (self.ceil + 1)  # 最小因数
#         self.primes = []
#         self.init_prime_factor()
#         return

#     def init_min_primes(self):
#         # 模板：计算 1 到 self.ceil 所有数字的最小质数因子 min_prime
#         # 模板: 收集 1 到 self.ceil 所有质数
#         for i in range(2, self.ceil + 1):
#             if not self.min_prime[i]:
#                 self.min_prime[i] = i
#                 self.primes.append(i)
#             for j in range(i * i, self.ceil + 1, i):
#                 if self.min_prime[j] == 0:
#                     self.min_prime[j] = i
#             for p in self.primes:
#                 if i * p > self.ceil:
#                     break
#                 self.min_prime[i * p] = p
#                 if i % p == 0:
#                     break

#     def init_prime_factor(self):
#         self.init_min_primes()
#         # 模板：计算 1 到 self.ceil 所有数字的质数分解（可选）
#         for num in range(2, self.ceil + 1):
#             i = num
#             while num > 1:
#                 p = self.min_prime[num]
#                 cnt = 0
#                 while num % p == 0:
#                     num //= p
#                     cnt += 1
#                 self.prime_factor[i].append([p, cnt])
#         return
